package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 1155. 掷骰子的N种方法
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/22 10:01
 */
public class NumRollsToTarget {

    public static void main(String[] args) {
        NumRollsToTarget test = new NumRollsToTarget();

        // 1
        int n = 1;
        int k = 6;
        int target = 3;

        // 222616187
//        int n = 30;
//        int k = 30;
//        int target = 500;

        // 6
//        int n = 2;
//        int k = 6;
//        int target = 7;

        int i = test.numRollsToTarget(n, k, target);
        System.out.println(i);

    }

    public int numRollsToTarget(int n, int k, int target) {
        int l = k * n;
        if (target > l) {
            return 0;
        }
        long[][] arr = new long[n][target + 1];
        long[] items = arr[0];
        for (int i = Math.min(target, k); i > 0; i--) {
            items[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            long[] lasts = arr[i - 1];
            int end = Math.min((i + 1) * k, target);
            int sum = 0;
            for (int j = (i + 1); j <= end; j++) {
                sum += lasts[j - 1];
                if (j - k - 1 >= 0) {
                    sum -= lasts[j - k - 1];
                    if (sum < 0) {
                        sum += 1000000007;
                    }
                }
                sum %= 1000000007;
                arr[i][j] = sum;
            }
        }
        return (int) arr[n - 1][target];
    }

}
